On duality and fractionality of multicommodity flows in directed networks

摘要

In this paper we address a topological approach to multiflow (multicommodityflow) problems in directed networks. Given a terminal weight $\mu$, we define ametrized polyhedral complex, called the directed tight span $T_{\mu}$, andprove that the dual of $\mu$-weighted maximum multiflow problem reduces to afacility location problem on $T_{\mu}$. Also, in case where the network isEulerian, it further reduces to a facility location problem on the tropicalpolytope spanned by $\mu$. By utilizing this duality, we establish theclassifications of terminal weights admitting combinatorial min-max relation(i) for every network and (ii) for every Eulerian network. Our result includesLomonosov-Frank theorem for directed free multiflows andIbaraki-Karzanov-Nagamochi's directed multiflow locking theorem as specialcases.